package interview.demo1;

/**
 * 希尔排序
 *  原理：根据一定的步长，将数据进行分组，然后对每组进行排序，
 *      在每一组数据都有序之后，缩小分组的步长，继续进行组内排序，
 *      直到步长缩短为0，相应的排序也就结束了。他可以显著的减少数据交换次数，加快排序速度。
 * @author
 * @create 2018-10-12 20:57
 **/
public class ShellSore {


    public static void main(String[] args) {

        int[] array = {10, 9, 8, 7};


        System.out.println("排序前的数组为：");
        for (int i : array) {
            System.out.print(i +" ");
        }
        SelleSore(array);
        System.out.println();
        System.out.println("排序后的数组为：");
        for (int i : array) {
            System.out.print(i+" ");
        }
    }


    public static void SelleSore(int[] array){

        int gap = array.length / 2;
        while (gap >= 1) {
            for (int i = gap; i < array.length; i++) {
                //如果一组中前面的数大于后面的数
                if (array[i - gap] > array[i]) {
                    //直接插入排序进行替换
                    for (int j = i-gap; (j >= 0) && (array[i] < array[j]); j =j-gap) {
                        //这里必须是用j+gap，不用是temp = array[i],如果这样的话会错误
                        int temp = array[j+gap];
                        array[j+gap] = array[j];
                        array[j] = temp;
                    }
                }
            }
            gap = gap / 2;
        }

    }
}
